package com.dyz.leetcode._14_binarySearchTree;

import com.dyz.leetcode.TreeNode;

public class _701_insertIntoBST {

    //  迭代
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root==null){return new TreeNode(val);}
        TreeNode curr = root;
        while (root!=null){
            if(val<curr.val && curr.left == null){
                curr.left = new TreeNode(val);
                return root;
            }else if(val>curr.val && curr.right==null){
                curr.right = new TreeNode(val);
                return root;
            }

            if(val<curr.val){
                curr = curr.left;
            }else {
                curr = curr.right;
            }
        }
    return root;
    }
    // 递归
    public TreeNode insertIntoBST1(TreeNode root, int val){
        if(root==null){return new TreeNode(val);}

        if(val<root.val){
            TreeNode left = insertIntoBST(root.left, val);
            root.left = left;
        }else {
            TreeNode right = insertIntoBST(root.right, val);
            root.right = right;
        }

        return root;
    }
}
